/************************************************************************

								Heroes IV
					  Copyright 2002, The 3DO Company

	------------------------------------------------------------------
  						 adventure_enemy_marker.cpp

	$Header: $

	$NoKeywords: $

 ************************************************************************/
// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "adventure_enemy_marker.h"

#include "adventure_map.h"
#include "adventure_object.h"
#include "army.h"
#include "creature_array.h"
#include "enum_operations.h"
#include "options.h"
#include "player.h"

#include "profile.h"
// ---------------------------------------------------------------
// abstract class to access enemy data from t_adventure_path_data
// ---------------------------------------------------------------
class t_adventure_path_finder_enemy_data_view
{
public:
	virtual bool compare_point( t_adventure_path_data const& old_point,
							    t_adventure_path_data const& new_point ) const = 0;
	virtual void set_point( t_adventure_path_data&			dest,
							t_adventure_path_data const&	source ) const = 0;

protected:
	~t_adventure_path_finder_enemy_data_view() {}
};

namespace
{
	// ---------------------------------------------------------------
	// class to access actual enemy data from t_adventure_path_data
	// ---------------------------------------------------------------

	class t_actual_enemy_data_view : public t_adventure_path_finder_enemy_data_view
	{
	public:
		virtual bool compare_point( t_adventure_path_data const& old_point,
							        t_adventure_path_data const& new_point ) const;
		virtual void set_point( t_adventure_path_data&			dest,
								t_adventure_path_data const&	source ) const;
	};

	bool t_actual_enemy_data_view::compare_point( t_adventure_path_data const& old_point,
												  t_adventure_path_data const& new_point ) const
	{
		if (!old_point.actual_enemy_adjacent)
			return false;

		if (old_point.actual_restricts_movement && !new_point.visible_restricts_movement)
		{
			return true;
		}
		if (!old_point.actual_restricts_movement && new_point.visible_restricts_movement)
		{
			return false;
		}
		return old_point.actual_enemy_distance <= new_point.move_cost;
	}

	void t_actual_enemy_data_view::set_point( t_adventure_path_data&		dest,
											  t_adventure_path_data const&	source ) const
	{
		dest.actual_restricts_movement = source.visible_restricts_movement;
		dest.actual_enemy_adjacent = true;
		dest.actual_enemy_direction = source.direction;
		dest.actual_enemy_distance = source.move_cost;
	}

	// ---------------------------------------------------------------
	// class to access visible enemy data from t_adventure_path_data
	// ---------------------------------------------------------------

	class t_visible_enemy_data_view : public t_adventure_path_finder_enemy_data_view
	{
	public:
		virtual bool			compare_point( t_adventure_path_data const& old_point,
										       t_adventure_path_data const& new_point ) const;
		virtual void set_point( t_adventure_path_data&			dest,
								t_adventure_path_data const&	source ) const;
	};

	bool t_visible_enemy_data_view::compare_point( t_adventure_path_data const& old_point,
										           t_adventure_path_data const& new_point ) const
	{
		if (!old_point.visible_enemy_adjacent)
			return false;

		if (old_point.visible_restricts_movement && !new_point.visible_restricts_movement)
		{
			return true;
		}
		if (!old_point.visible_restricts_movement && new_point.visible_restricts_movement)
		{
			return false;
		}
		return old_point.visible_enemy_distance <= new_point.move_cost;
	}

	void t_visible_enemy_data_view::set_point( t_adventure_path_data&		dest,
											  t_adventure_path_data const&	source ) const
	{
		dest.visible_restricts_movement = source.visible_restricts_movement;
		dest.visible_enemy_adjacent = true;
		dest.visible_enemy_direction = source.direction;
		dest.visible_enemy_distance = source.move_cost;
	}

	// ---------------------------------------------------------------
	// Compare points by movement cost
	// ---------------------------------------------------------------
	class t_compare_move_cost
	{
	public:
		bool operator()( t_adventure_path_point const& left, 
		                 t_adventure_path_point const& right ) const
		{
			return left.move_cost > right.move_cost;
		}
	};

	// ---------------------------------------------------------------
	// ---------------------------------------------------------------
	bool blocked_by_shroud(
		t_creature_array const &	army,
		t_adventure_tile const &	tile,
		t_path_search_type			path_type )
	{
		if (   ( path_type != k_path_search_standard && path_type != k_path_search_caravan ) 
			|| !get_enable_shroud() )
			return false;

		t_player const * owner = army.get_owner();
		return		owner != 0
				&&	tile.get_visibility( owner->get_team() ) == k_tile_never_explored;
	}


} // unnamed namespace

// ---------------------------------------------------------------
// data structure for adventure path finder
// ---------------------------------------------------------------
t_adv_path_sector::t_adv_path_sector()
{
	memset( m_data, 0, sizeof( m_data ));
	m_enemies_marked = false;
}

// ---------------------------------------------------------------
// data structure for adventure path finder
// ---------------------------------------------------------------

t_adv_path_map::t_adv_path_map( int size, int levels )
{
	int total_size;

	m_size = (size + k_adv_path_sector_mask) >> k_adv_path_sector_shift;
	m_levels = levels;
	total_size = m_size * m_size * m_levels * 2;
	assert( total_size > 0 );
	m_data.resize( total_size );
}

// ---------------------------------------------------------------
// data structure for adventure path finder
// ---------------------------------------------------------------
void t_adv_path_map::clear()
{
	int total_size;

	m_data.clear();
	total_size = m_size * m_size * m_levels * 2;
	assert( total_size > 0 );
	m_data.resize( total_size );
}

t_adv_path_sector* t_adv_path_map::get_sector( t_adv_map_point const& point, 
											   bool mark_enemies ) const
{
	int index = calculate_data_index( point );

	t_sector_ptr& sector_ptr = m_data[index];

	if (sector_ptr.get() == 0)
		sector_ptr = new t_adv_path_sector;
	if (mark_enemies && !sector_ptr->enemies_are_marked())
	{
		t_adv_map_point top_left = point;

		top_left.column &= ~k_adv_path_sector_mask;
		top_left.row &= ~k_adv_path_sector_mask;
		// mark all enemies within this sector, plus enemies within 2 tiles in
		// every direction.
		top_left.column -= k_army_attack_radius;
		top_left.row -= k_army_attack_radius;
		sector_ptr->set_enemies_marked( true );
		// shortcut: if this sector has been marked on the ground level, it's
		// also been marked at bridge level, and vice-versa.
		t_adv_map_point		alternate_point = point;
		int					alternate_index;
		t_adv_path_sector*	alternate_sector;
		
		alternate_point.on_bridge = !point.on_bridge;
		alternate_index = calculate_data_index( alternate_point );
		alternate_sector = m_data[alternate_index];
		if (alternate_sector == 0 || !alternate_sector->enemies_are_marked())
			m_parent->mark_enemies( top_left, k_adv_path_sector_size + 2 * k_army_attack_radius,
								    k_adv_path_sector_size + 2 * k_army_attack_radius);
	}
	return sector_ptr;
}

// ---------------------------------------------------------------
// data structure for adventure path finder
// ---------------------------------------------------------------
// ---------------------------------------------------------------
// class to mark enemies and find paths for adventure map
// ---------------------------------------------------------------
t_adventure_enemy_marker::t_adventure_enemy_marker( t_adventure_map& map )
	: m_map( map ), m_data( map.get_size(), map.get_num_levels() ),
	  m_path_type(k_path_search_standard), m_initialized(false)
{
	m_data.set_parent( this );
}

// ---------------------------------------------------------------
// class to mark enemies and find paths for adventure map
// Initialize enemy markings
// ---------------------------------------------------------------
void t_adventure_enemy_marker::initialize()
{
	if (m_initialized)
		return;
	if (m_army == 0)
		return;


	m_initialized = true;

	// clear array
	m_data.clear();
}

// ---------------------------------------------------------------
// find which directions are blocked from a point
// ---------------------------------------------------------------
void t_adventure_enemy_marker::find_blocked_directions( t_adventure_path_point const&	point,
														t_creature_array const&			army,
														bool							is_ship,
														t_adv_map_point*				adjacent_points,
														bool*							blocked,
														bool*							valid_point )
{
	t_direction direction;

	for (direction = t_direction(0); direction < k_direction_count; enum_incr( direction ))
	{
		t_adv_map_point new_point = point + get_direction_offset( direction );
		
		valid_point[direction] = m_map.is_valid( new_point );
		blocked[direction] = !valid_point[direction];
		if (valid_point[direction])
		{
			t_adventure_tile const& tile = m_map[new_point];

			if ( m_map.is_ramp_open( point, direction ) )
				new_point.on_bridge = !new_point.on_bridge;

			adjacent_points[direction] = new_point;
			if (is_ship && tile.has_ramp())
				blocked[direction] = true;
			else if (	tile.blocks_army( army, m_map, new_point.on_bridge, m_path_type )
					||	blocked_by_shroud( army, tile, m_path_type )
					||  m_map.is_blocked( point, direction ))
			{
				blocked[direction] = true;
			}
		}
	}
}


// ---------------------------------------------------------------
// class to mark enemies and find paths for adventure map
// ---------------------------------------------------------------

void t_adventure_enemy_marker::mark_enemy( t_army const*			enemy,
										   t_enemy_data_view const&	enemy_data_view,
										   t_skill_mastery			stealth_level )
{
	t_adventure_path_point              point( enemy->get_position() );
	t_adv_map_point		                start;

	start = point;
	point.move_cost = 0;
	point.visited = true;
	point.visible_restricts_movement = true;
	enemy_data_view.set_point( m_data.get( point, false ), point );
	if (enemy->get_anti_stealth_level() + 1 < stealth_level)
		return;

	t_adv_map_point						adjacent_points[k_direction_count];
	bool								blocked[k_direction_count];
	t_map_point_2d                      delta;
	t_direction							direction;
	bool								enemy_restricts_movement;
	bool								is_ship;
	t_adventure_path_data				map[k_army_attack_array_size][k_army_attack_array_size];
	int									new_delta_sum;
	int									old_delta_sum;
	std::vector<t_adventure_path_point> open_points;
	t_direction							opposite_direction;
	bool								valid_point[k_direction_count];

	is_ship = m_map.is_ocean( point ) && !point.on_bridge;
	memset( &map, 0, sizeof(map));
	map[k_army_attack_radius][k_army_attack_radius] = point;
	open_points.push_back( point );
	while (!open_points.empty())
	{
		point = open_points.back();
		open_points.pop_back();

		find_blocked_directions( point, *enemy, is_ship, adjacent_points, blocked, 
			                     valid_point );
		old_delta_sum = abs( point.column - start.column ) + abs( point.row - start.row );

		for (direction = t_direction(0); direction < k_direction_count; enum_incr( direction ))
		{
			if (!valid_point[direction])
				continue;

			t_adventure_path_point new_point( adjacent_points[direction] );

			enemy_restricts_movement = true;
			// check if this tile is blocked
			if (blocked[direction])
			{
				// if there is no trigger here, but the diagonal might be open...
				if (m_map.corners_block( point, new_point, direction ))
					enemy_restricts_movement = false;
				if (m_map.get_trigger_object( point, direction, enemy ) == 0)
				{
					// if this isn't a diagonal move, it's really blocked.
					if ((direction & 1) == 0)
						continue;
				}
			}

			delta.column = new_point.column - start.column + k_army_attack_radius;
			delta.row    = new_point.row - start.row + k_army_attack_radius;
			if (delta.column < 0 || delta.column >= k_army_attack_array_size
				|| delta.row < 0 || delta.row >= k_army_attack_array_size)
				continue;

			// this is normally bad pathfinding, but in this case we want to exclude
			// convulted paths from the activation radius, so (for example), the army
			// doesn't move around a wall to activate.
			// In aid of that, we don't allow paths where the new point is
			// closer to the army than the old point, in simple air distance.
			int delta_column = abs( new_point.column - start.column );
			int delta_row = abs( new_point.row - start.row );
			new_delta_sum = delta_column + delta_row;
			if (new_delta_sum < old_delta_sum)
				continue;

			opposite_direction = opposite( direction );

			int move_cost = 2;

			if ((direction & 1) != 0)
				move_cost = 3;
			new_point.move_cost = point.move_cost + move_cost;
			assert( new_point.move_cost > 0 && new_point.move_cost < 64 );
			new_point.visited = true;
			new_point.visible_restricts_movement = enemy_restricts_movement;
			new_point.last_point = point;
			new_point.direction = opposite_direction;

			t_adventure_path_data& old_point = map[delta.row][delta.column];

			if (old_point.visited)
			{
				if (old_point.visible_restricts_movement && !enemy_restricts_movement)
					continue;
				if ((old_point.visible_restricts_movement || !enemy_restricts_movement)
					&& old_point.move_cost <= new_point.move_cost)
					continue;
			}

			t_adventure_path_data& map_point = m_data.get( new_point, false );

			// check if we can legally enter this type of square
			if (is_ship)
			{
				if (!m_map.is_ocean( new_point ))
					continue;
			}
			else
			{
				// armies cannot enter water unless the new point is a boat.
				if (!new_point.on_bridge && !m_map.is_land( new_point ))
					continue;
			}

			// This is a nasty little hack to take into account the fact that
			// the army attacking the one we're marking doesn't need to obey 
			// the diagonal rule when actually entering this army's tile.
			if (enemy_restricts_movement && delta_column <= 1 && delta_row <= 1
				&& point != start && point.last_point == start && (direction & 1) == 0
				&& start.on_bridge == new_point.on_bridge)
			{
				if ( clockwise( new_point.direction, 2 ) == point.direction
				     || counter_clockwise( new_point.direction, 2 ) == point.direction )
				{
					// we're within 1 tile, but not pointing to the start tile.
					// we're not pointing diagonally, we're pointing orthagonally
					// to a tile which does point to the start tile.
					// last point is start.
					new_point.last_point = start;
					// move cost is 3, for a diagonal move.
					new_point.move_cost = 3;
					// adjust the direction to the correct diagonal.
					if (counter_clockwise( new_point.direction, 2 ) == point.direction )
						new_point.direction = counter_clockwise( new_point.direction );
					else
						new_point.direction = clockwise( new_point.direction );
				}
			}

			if (enemy_data_view.compare_point( map_point, new_point ))
				continue;

			old_point = new_point;
			enemy_data_view.set_point( map_point, new_point );

			if (blocked[direction])
				continue;

			std::vector<t_adventure_path_point>::iterator index;

			index = std::lower_bound( open_points.begin(), open_points.end(), new_point,
									  t_compare_move_cost() );
			open_points.insert( index, new_point );

		}
	}
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
void t_adventure_enemy_marker::mark_enemies( t_adv_map_point const& top_left, int rows, 
											 int columns )
{
	if (m_path_type == k_path_search_enemy_activation
		|| m_path_type == k_path_search_place_army
		|| m_path_type == k_path_search_player_danger
		|| m_path_type == k_path_search_ai_threat)
		return;

	if (m_path_type == k_path_search_ai_guard_danger
			|| m_path_type == k_path_search_ai_danger )
	{
		t_army* army = m_army->get_army();
		if ( army != NULL )
			mark_enemy( m_army->get_army(), t_actual_enemy_data_view(), m_army->get_anti_stealth_level() );
		return;			
	}

	t_army_list::iterator	index = m_map.get_armies_begin();
	t_army_list::iterator	end	= m_map.get_armies_end();
	t_player*				owner = m_army->get_owner();
	int						owner_team = owner != 0 ? owner->get_team() : -1;
	t_army*					army;
	t_skill_mastery			stealth_level = m_army->get_stealth_level();
	int						level = top_left.level;
	int						top = top_left.row;
	int						left = top_left.column;
	int						right = top_left.column + columns;
	int						bottom = top_left.row + rows;

	declare_timer( timer_1, "mark enemies" );

	for (; index != end; index++)
	{
		army = *index;

		t_adv_map_point const& position = army->get_position();

		if (position.level != level)
			continue;
		if (position.row < top_left.row || position.row >= bottom
			|| position.column < top_left.column || position.column >= right)
			continue;
		if (same_team( army->get_owner(), owner ) || army->is_graveyard() || army->empty())
			continue;

		// Mark this as an actual enemy
		mark_enemy( army, t_actual_enemy_data_view(), stealth_level );

		// Mark this as a visible enemy if it's visible
		if ( !army->hidden_by_fog_of_war( owner_team ) )
			mark_enemy( army, t_visible_enemy_data_view(), stealth_level );
	}
}

// ---------------------------------------------------------------
// class to mark enemies and find paths for adventure map
// ---------------------------------------------------------------
void t_adventure_enemy_marker::set_army( t_creature_array* army )
{
	if (m_army == army)
		return;
	m_army = army;
	m_initialized = false;
}

void t_adventure_enemy_marker::set_path_type( t_path_search_type path_type )
{
	if (m_path_type == path_type)
		return;
	m_initialized = false;
	m_path_type = path_type;
}

